//
// Created by weslywang on 2020/5/8.
//

#include "../common/common.h"

int maxPathSum(TreeNode *root, int &result) {
    if (!root) {
        return 0;
    }
    long x1 = INT32_MIN, x2 = INT32_MIN, mid = root->val, midLeft = root->val, midRight = root->val;
    long store[6];
    if (root->left) {
        x1 = maxPathSum(root->left, result);
    }
    if (root->right) {
        x2 = maxPathSum(root->right, result);
    }
    if (x1 != INT32_MIN) {
        mid += x1;
        midLeft += x1;
    }
    if (x2 != INT32_MIN) {
        mid += x2;
        midRight += x2;
    }
    store[0] = midLeft;
    store[1] = midRight;
    store[2] = mid;
    store[3] = x1;
    store[4] = x2;
    store[5] = result;
    long maxNum = root->val, maxRe = root->val;
    for (int i = 0; i < 6; i++) {
        maxNum = store[i] > maxNum ? store[i] : maxNum;
        maxRe = i < 2 && store[i] > maxRe ? store[i] : maxRe;
    }
    result = (int) maxNum;
//    cout << root->val << ",左边 " << midLeft << ",右边 " << midRight << ",返回 " << maxRe << endl;
    return (int) maxRe;
}

int maxPathSum(TreeNode *root) {
    int result = INT32_MIN;
    maxPathSum(root, result);
    return result;
}

int main() {
    Common common;
    int a[] = {1, 2, 3, 4, 5};
    vector<vector<int>> numList = common.loadData();
    for (int i = 0; i < numList.size(); i++) {
        TreeNode *root = common.makeTree(numList[i]);
        cout << maxPathSum(root) << endl;
        cout << "**************" << endl;
    }
    return 0;
}